from math import inf


class Solution:
    def findRotateSteps(self, ring: str, key: str) -> int:
        n = len(ring)
        f = [inf] * n
        f[0] = 0
        for k in key:
            nf = [inf] * n
            for i, v in enumerate(f):
                if v < inf:
                    for j in range(n):
                        forward = (i + j) % n
                        if ring[forward] == k:
                            nf[forward] = min(nf[forward], f[i] + j + 1)
                        backwards = (i - j) % n
                        if ring[backwards] == k:
                            nf[backwards] = min(nf[backwards], f[i] + j + 1)
            f = nf
        return min(f)


s = Solution()
print(s.findRotateSteps(ring="godding", key="gd"))
